A viterbi decoder is a maximum likelihood decoder that provides forward error correction. Viterbi decoding is used in decoding a sequence of encoded symbols, such as a bit stream. The bit stream can represent encoded information in a system that is transmitted through various media in a system with each set of bits representing a symbol instant. Viterbi decoding is employed in digital communications over communication channels such as satellite-to-earth, cellular telephony, microprocessor-to-disk, modem-to-modem and others. Viterbi decoders have been implemented on hardware microprocessors, microcontrollers, and digital signal processors. Viterbi decoding is well-known and applications can be found in U.S. Pat. Nos. 5,490,178; 5,454,014; 5,559,837; 5,465,275; 5,471,500; 5,144,644; and 4,493,082, the disclosures of which are hereby incorporated by reference.
A viterbi implementation consists of four steps: branch and path metric computation; a compare-select operation; a minimum or maximum state cost determination; and a traceback operation to determine a decoded symbol. In the decoding process, a viterbi decoder works back through a sequence of possible bit sequences at each symbol instant to determine which bit sequence was most likely to have been transmitted. The possible transitions from a state at one symbol instant, or present state, to a state at a next, subsequent symbol instant, or next state, is limited. Each possible transition from a present state to a next state can be shown graphically and is defined as a branch. A sequence of interconnected branches is defined as a path. Each state can only transition to a limited number of next states upon receipt of the next bit or bits in the bitstream. Thus, some branches survive to become part of a path and other branches do not survive to become part of a path. By eliminating those transitions or branches that are not permissible, computational efficiency can be achieved in determining the most likely paths to survive. A viterbi decoder typically defines and calculates a branch metric associated with each branch and employs the branch metric to determine which paths survive and which paths do not survive.
A branch metric is calculated at each symbol instant for each possible branch. Each path has an associated metric or accumulated cost that is updated at each symbol instant. For each possible transition, the accumulated cost for the next state is calculated as a sum of the branch metric and the path accumulated cost at the present state origin of the branch metric. A maximum or minimum extremum may be selected.
While several branches, and several paths, survive the transition from one symbol instant to the next symbol instant, a traceback operation through the surviving paths is employed to select the most likely bit or bit sequence to have been transmitted. The sequential symbol instants may be represented in an array referred to as a trellis. Identifying the extremum accumulated cost path starting with a given symbol instant is referred to as a traceback operation. The number of symbol instants back through the trellis that the extremum accumulated cost path extends is the length, or depth, of the traceback operation. At the end of the traceback operation, the individual state in the trellis associated with the surviving path that originated at an extremum accumulated cost is translated into the most likely bit or bits to have been transmitted in that symbol instant. The bit or groups of bits is referred to as a decoded symbol.
In communications applications employing viterbi decoding in which a single bit is transmitted each symbol instant, two possible present states can transition, or branch, into a single next state and a single bit is sufficient to uniquely determine which of the two possible branches transitioned into a given next state.
What is needed is an efficient method for identifying an extremum accumulated cost, such as a maximum or minimum, for use in decoding a received digital signal in a viterbi decoder.